package LeetCode热题HOT100;

public class p279完全平方数 {
    public int numSquares(int n) {
        //动态规划
        int[] dp=new int[n+1];
        dp[0]=0;

        for (int i = 1; i <=n ; i++) {
            //先背包
            //dp[i]代表  完全平方数相加和为i 的最少完全平方数的个数
            dp[i]=i;//和为 i的最坏情况
            for (int j = 1; i-j*j>=0; j++) {
                //再物品
                dp[i]=Math.min(dp[i],dp[i-j*j]+1);//+1 加的是dp[j*j] 这个完全平方数的一种情况
            }
        }
        return dp[n];

    }
}
